package checker.algorithms.sort.primarySort;

import checker.algorithms.sort.SortBase;

public class Insertion extends SortBase {
    /**
     * best:
     *  i执行n，j不执行，则循环n次
     *  => n
     * worst:
     *  j每次执行i-0，则为：1+...+n = n(n-1)/2
     *  => n*n
     *
     *
     * @param a
     */
    @Override
    public void sort(Comparable[] a) {
        int length = a.length;
        for (int i = 0; i < length; i++) {
            // 在0到i中找到位置，如果不是升序，交换，直到j=0
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }

        System.out.println(isSorted(a));
    }

    public static void main(String[] args) {
        new Insertion().run();
    }
}
